package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import util.LogUtils;
import util.datastructure.ListNode;

/*
 * 
原题
	Given a linked list, return the node where the cycle begins. If there is no cycle, return null. 
题目大意	
	找到 环的起始节点
解题思路

	 @wangxiaotao的图不错，借用一下，公式不太清楚。
	串长a + n，其中n为循环，当a + b步的慢指针与快指针相遇时，快指针已经走过了k圈。
	即a + b + k * n = 2 * (a+b)，求a，得到a = k * n - b。
	也就是X走a步，等于Z位置上的指针再走k圈，相遇于Y点。 
	
	即：
	   我们判断环的存在，即用slow和fast两个指针，设定步长fast=2;slow=1;如果两个指针可以相遇则环存在，
	   	此时如果二者相遇我们只需将slow=head;同时设置两者步长都为1，则两者再次相遇的节点即为环的开始节点。
　　https://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad
 * @Date 2017-10-09 00：30
 */
public class _142_Linked_List_Cycle_II {
    public ListNode detectCycle(ListNode head) {
    	if (head == null)	return  null;
    	ListNode fast = head, slow = head;
    	while (fast!=null && fast.next!=null) {
    		fast = fast.next.next;
    		slow = slow.next;
    		if (fast == slow) {
    			//有环
    			ListNode slow2 = head;
    			while (true) {
    				if (slow2 == slow)	return slow2;	//环起点
    				slow2 = slow2.next;
    				slow = slow.next;
    			}
    		}
    	}
		return null;						//无环、返回null
    }
	
	public static void main(String[] args) {
		_142_Linked_List_Cycle_II obj = new _142_Linked_List_Cycle_II();
		LogUtils.println("结果", 
				obj.detectCycle(

						new ListNode(1)
				));
	}

}
